package class01;

import java.util.Arrays;

/**
 * @ClassName class01.Code04_BSExist
 * @Description TODO
 * @Author zhengjiabin
 * @Date 2021/6/1 21:12
 * @Version 1.0
 **/
public class Code04_BSExist {

    // 在有序数组中找一个数存在的最左侧位置
    public static boolean exist(int[] arr, int num){
        if (arr == null || arr.length == 0){
            return false;
        }
        int left = 0;
        int right = arr.length - 1;
        int mid = 0;
        while (left <= right){
            mid = left + ((right - left) >> 1);
            if (arr[mid] == num){
                return true;
            }else if (arr[mid] > num){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return arr[mid] == num;
    }

    // 对数器
    public static boolean checkNum(int[] arr, int value){
        for (int i : arr) {
            if (i == value) {
                return true;
            }
        }
        return false;
    }


    // 随机生成数组
    public static int[] generateRandomArray(int maxSize, int maxValue){
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(((maxValue + 1) * Math.random()) - ((maxValue + 1) * Math.random()));
        }
        return arr;
    }


    //系统提供比较器
    public static void comparator(int[] arr){
        Arrays.sort(arr);
    }


    // 数组打印
    public static void printArray(int[] arr){
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }


    public static void main(String[] args) {
        // 校验样本次数
        int count = 500000;
        // 数组随机最大size
        int maxSize = 100;
        // 数组随机最大值
        int maxValue = 100;
        // 两个排序算法是否使数组完全相同的标志位
        boolean flag = true;
        for (int i = 0; i < count; i++) {
            // 生成随机数组
            int[] arr = generateRandomArray(maxSize, maxValue);
            // 数组排序
            comparator(arr);
            // 随机生成value
            int value = (int)((Math.random() * maxValue + 1) - (Math.random() * maxValue + 1));
            // 比较两个方法找到的数组下标是否相同
            if (checkNum(arr, value) != exist(arr, value)){
                // 标志位置为false
                flag = false;
                // 打印数组
                System.out.println("arr: ");
                printArray(arr);
                // 打印value
                System.out.println("value: ");
                System.out.println(value);
                //打印二分查找方法找出的值
                System.out.println("二分查找找出的index: ");
                System.out.println(exist(arr, value));
                // 打印循环遍历找找出的值
                System.out.println("arr: ");
                System.out.println(checkNum(arr, value));
                break;
            }
    }
        System.out.println(flag ? "二分查找与循环遍历50w次找到的数值相同":"二分查找与循环遍历50w次找到的index不相同");
    }
}
